Voronoi diagrams with barriers and on polyhedra for minimal path planning
Identifieur interne : 001437 ( Main/Exploration ); précédent : 001436; suivant : 001438Voronoi diagrams with barriers and on polyhedra for minimal path planning
Auteurs : W. Randolph Franklin [États-Unis] ; Varol Akman [États-Unis] ; Colin Verrilli [États-Unis]Source :
- The Visual Computer [ 0178-2789 ] ; 1985-08-01.
English descriptors
- Teeft :
- Adjacent barriers, Akman, Algorithm, Annual symposium, Approximation techniques, Artificial intelligence, Barrier, Base outline, Binary search, Boundary lines, Closest point, Comp graph image processing, Computational geometry, Computer science, Contact list, Contact lists, Contact vertices, Convex, Convex hull, Convex polyhedron, Cube, Diagram, Dihedral angle, Dihedral principle, Euclidean space, Evolvent, Execution time, Face graph, Face visit sequence, Findpath problem, Finite number, Free space, General point, Goal point, Good representation, Hyperbola, Hyperbolic sections, Ieee, Ieee systems, Image point, Image processing, Information processing letters, Inst, Interpolation search, Line segment, Mathematical sciences, Minimal path, Minimal path problem, Minimal paths, Motion planning, Multiple barriers, Multiple sources, Node, Obstruction, Original region, Other hand, Other point, Path problem, Piano movers, Planar, Planar graph, Planar graphs, Planar search algorithms, Planar subdivision, Point voronoi diagram, Polygon, Polygonal, Polygonal barriers, Polyhedral, Polyhedral obstacles, Polyhedral surfaces, Polyhedron, Preprocessing, Preprocessing time, Quadric surfaces, Query point, Recent work, Rectilinear barriers, Rensselaer polytechnic inst, Ridge line, Ridge lines, Robotics, Same barrier, Same side, Scan line, Search time, Shadow line, Shadow lines, Sharir, Shortest, Shortest path, Shortest paths, Simple face visit sequences, Simple sequences, Simple visit sequences, Single source, Source points, Special case, Stanford univ, Straight edges, Straight line, Straight line segments, Straight lines, Trajectory calculation, Undirected graph, Univ, Visible source, Visible sources, Voronoi, Voronoi diagram, Voronoi diagrams, Yale univ, York univ.
Abstract
Abstract: Two generalizations of the Voronoi diagram in two dimensions (E2) are presented in this paper. The first allows impenetrable barriers that the shortest path must go around. The barriers are straight line segments that may be combined into polygons and even mazes. Each region of the diagram delimits a set of points that have not only the same closest existing point, but have the same topology of shortest path. The edges of this diagram, which has linear complexity in the number of input points and barrier lines, may be hyperbolic sections as well as straight lines. The second construction considers the Voronoi diagram on the surface of a convex polyhedron, given a set of fixed source points on it. Each face is partitioned into regions, such that the shortest path to any goal point in a given region from the closest fixed source point travels over the same sequence of faces to the same closest point.
Url:
DOI: 10.1007/BF01898357
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000391
- to stream Istex, to step Curation: 000368
- to stream Istex, to step Checkpoint: 001208
- to stream Main, to step Merge: 001441
- to stream Main, to step Curation: 001437
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Voronoi diagrams with barriers and on polyhedra for minimal path planning</title><author><name sortKey="Franklin, W Randolph" sort="Franklin, W Randolph" uniqKey="Franklin W" first="W. Randolph" last="Franklin">W. Randolph Franklin</name></author><author><name sortKey="Akman, Varol" sort="Akman, Varol" uniqKey="Akman V" first="Varol" last="Akman">Varol Akman</name></author><author><name sortKey="Verrilli, Colin" sort="Verrilli, Colin" uniqKey="Verrilli C" first="Colin" last="Verrilli">Colin Verrilli</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:2620AE042C36C95023E40136F1FDF221A0C7553B</idno><date when="1985" year="1985">1985</date><idno type="doi">10.1007/BF01898357</idno><idno type="url">https://api.istex.fr/document/2620AE042C36C95023E40136F1FDF221A0C7553B/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">000391</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000391</idno><idno type="wicri:Area/Istex/Curation">000368</idno><idno type="wicri:Area/Istex/Checkpoint">001208</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001208</idno><idno type="wicri:doubleKey">0178-2789:1985:Franklin W:voronoi:diagrams:with</idno><idno type="wicri:Area/Main/Merge">001441</idno><idno type="wicri:Area/Main/Curation">001437</idno><idno type="wicri:Area/Main/Exploration">001437</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Voronoi diagrams with barriers and on polyhedra for minimal path planning</title><author><name sortKey="Franklin, W Randolph" sort="Franklin, W Randolph" uniqKey="Franklin W" first="W. Randolph" last="Franklin">W. Randolph Franklin</name><affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Electrical, Computer, and Systems Engineering Dep., Rensselaer Polytechnic Institute, 12180, Troy, New York</wicri:regionArea><placeName><region type="state">État de New York</region></placeName></affiliation></author><author><name sortKey="Akman, Varol" sort="Akman, Varol" uniqKey="Akman V" first="Varol" last="Akman">Varol Akman</name><affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Electrical, Computer, and Systems Engineering Dep., Rensselaer Polytechnic Institute, 12180, Troy, New York</wicri:regionArea><placeName><region type="state">État de New York</region></placeName></affiliation></author><author><name sortKey="Verrilli, Colin" sort="Verrilli, Colin" uniqKey="Verrilli C" first="Colin" last="Verrilli">Colin Verrilli</name><affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Electrical, Computer, and Systems Engineering Dep., Rensselaer Polytechnic Institute, 12180, Troy, New York</wicri:regionArea><placeName><region type="state">État de New York</region></placeName></affiliation></author></analytic><monogr></monogr><series><title level="j">The Visual Computer</title><title level="j" type="sub">International Journal of Computer Graphics</title><title level="j" type="abbrev">The Visual Computer</title><idno type="ISSN">0178-2789</idno><idno type="eISSN">1432-2315</idno><imprint><publisher>Springer-Verlag</publisher><pubPlace>Berlin/Heidelberg</pubPlace><date type="published" when="1985-08-01">1985-08-01</date><biblScope unit="volume">1</biblScope><biblScope unit="issue">2</biblScope><biblScope unit="page" from="133">133</biblScope><biblScope unit="page" to="150">150</biblScope></imprint><idno type="ISSN">0178-2789</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0178-2789</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="Teeft" xml:lang="en"><term>Adjacent barriers</term><term>Akman</term><term>Algorithm</term><term>Annual symposium</term><term>Approximation techniques</term><term>Artificial intelligence</term><term>Barrier</term><term>Base outline</term><term>Binary search</term><term>Boundary lines</term><term>Closest point</term><term>Comp graph image processing</term><term>Computational geometry</term><term>Computer science</term><term>Contact list</term><term>Contact lists</term><term>Contact vertices</term><term>Convex</term><term>Convex hull</term><term>Convex polyhedron</term><term>Cube</term><term>Diagram</term><term>Dihedral angle</term><term>Dihedral principle</term><term>Euclidean space</term><term>Evolvent</term><term>Execution time</term><term>Face graph</term><term>Face visit sequence</term><term>Findpath problem</term><term>Finite number</term><term>Free space</term><term>General point</term><term>Goal point</term><term>Good representation</term><term>Hyperbola</term><term>Hyperbolic sections</term><term>Ieee</term><term>Ieee systems</term><term>Image point</term><term>Image processing</term><term>Information processing letters</term><term>Inst</term><term>Interpolation search</term><term>Line segment</term><term>Mathematical sciences</term><term>Minimal path</term><term>Minimal path problem</term><term>Minimal paths</term><term>Motion planning</term><term>Multiple barriers</term><term>Multiple sources</term><term>Node</term><term>Obstruction</term><term>Original region</term><term>Other hand</term><term>Other point</term><term>Path problem</term><term>Piano movers</term><term>Planar</term><term>Planar graph</term><term>Planar graphs</term><term>Planar search algorithms</term><term>Planar subdivision</term><term>Point voronoi diagram</term><term>Polygon</term><term>Polygonal</term><term>Polygonal barriers</term><term>Polyhedral</term><term>Polyhedral obstacles</term><term>Polyhedral surfaces</term><term>Polyhedron</term><term>Preprocessing</term><term>Preprocessing time</term><term>Quadric surfaces</term><term>Query point</term><term>Recent work</term><term>Rectilinear barriers</term><term>Rensselaer polytechnic inst</term><term>Ridge line</term><term>Ridge lines</term><term>Robotics</term><term>Same barrier</term><term>Same side</term><term>Scan line</term><term>Search time</term><term>Shadow line</term><term>Shadow lines</term><term>Sharir</term><term>Shortest</term><term>Shortest path</term><term>Shortest paths</term><term>Simple face visit sequences</term><term>Simple sequences</term><term>Simple visit sequences</term><term>Single source</term><term>Source points</term><term>Special case</term><term>Stanford univ</term><term>Straight edges</term><term>Straight line</term><term>Straight line segments</term><term>Straight lines</term><term>Trajectory calculation</term><term>Undirected graph</term><term>Univ</term><term>Visible source</term><term>Visible sources</term><term>Voronoi</term><term>Voronoi diagram</term><term>Voronoi diagrams</term><term>Yale univ</term><term>York univ</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: Two generalizations of the Voronoi diagram in two dimensions (E2) are presented in this paper. The first allows impenetrable barriers that the shortest path must go around. The barriers are straight line segments that may be combined into polygons and even mazes. Each region of the diagram delimits a set of points that have not only the same closest existing point, but have the same topology of shortest path. The edges of this diagram, which has linear complexity in the number of input points and barrier lines, may be hyperbolic sections as well as straight lines. The second construction considers the Voronoi diagram on the surface of a convex polyhedron, given a set of fixed source points on it. Each face is partitioned into regions, such that the shortest path to any goal point in a given region from the closest fixed source point travels over the same sequence of faces to the same closest point.</div></front></TEI><affiliations><list><country><li>États-Unis</li></country><region><li>État de New York</li></region></list><tree><country name="États-Unis"><region name="État de New York"><name sortKey="Franklin, W Randolph" sort="Franklin, W Randolph" uniqKey="Franklin W" first="W. Randolph" last="Franklin">W. Randolph Franklin</name></region><name sortKey="Akman, Varol" sort="Akman, Varol" uniqKey="Akman V" first="Varol" last="Akman">Varol Akman</name><name sortKey="Verrilli, Colin" sort="Verrilli, Colin" uniqKey="Verrilli C" first="Colin" last="Verrilli">Colin Verrilli</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Sarre/explor/MusicSarreV3/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001437 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 001437 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Sarre
|area= MusicSarreV3
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:2620AE042C36C95023E40136F1FDF221A0C7553B
|texte= Voronoi diagrams with barriers and on polyhedra for minimal path planning
}}
| This area was generated with Dilib version V0.6.33. |  |